import bisect
import collections
class Solution(object):
    def waysToPartition(self, nums, k):
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] + nums[i - 1]
        d = collections.defaultdict(list)
        for i in range(1, n + 1):
            d[prefix[i]].append(i - 1)
        ans = 0
        t_sum = sum(nums)
        if t_sum % 2 == 0:
            mid_sum = t_sum // 2
            right_index = bisect.bisect_left(d[mid_sum], n - 1)
            ans += right_index
        for i in range(n):
            new_t_sum = t_sum + k - nums[i]
            temp = 0
            if new_t_sum % 2 == 0:
                mid_sum = new_t_sum // 2 - (k - nums[i])
                left_index = bisect.bisect_left(d[mid_sum], i)
                right_index = bisect.bisect_left(d[mid_sum], n - 1)
                temp += max(0, right_index - left_index)
                mid_sum = new_t_sum // 2
                right_index = bisect.bisect_left(d[mid_sum], i)
                temp += right_index
                ans = max(ans, temp)
        return ans


data = Solution()
nums = [2,-1,2]
k = 3
print(data.waysToPartition(nums, k))
nums = [0, 0, 0]
k = 1
print(data.waysToPartition(nums, k))
nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14]
k = -33
print(data.waysToPartition(nums, k))
nums = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,30827,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
k = 0
print(data.waysToPartition(nums, k))
nums = [0,0,0,0,0,0]
k = 0
print(data.waysToPartition(nums, k))
nums = [0,3,0,-3,0]
k = 0
print(data.waysToPartition(nums, k))